package com.yx.study.leet.questionList.questionTwo;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 57. 插入区间
 * https://leetcode.cn/problems/insert-interval/description/
 */
public class Solution57 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 重叠区间比较
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false; // 是否交集
        List<int[]> ansList = new ArrayList<>();
        for (int[] interval : intervals) { // {{1,3},{6,9}}  {2,5}
            if (interval[0] > right) {
                if (!placed) { // 插入区间右侧,且无交集
                    ansList.add(new int[]{left, right});
                    placed = true;
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 插入区间左侧,无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集,需要计算并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) { // 合并后为最后一个并集
            ansList.add(new int[]{left, right});
        }
        int[][] res = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); i++) {
            res[i] = ansList.get(i);
        }
        return res;
    }

    @Test
    public void test() {
        int[][] intervals = new int[][]{{1, 3}, {6, 9}};
        int[] newInterval = new int[]{2, 5};
//        intervals = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
//        newInterval = new int[]{4, 8};
        newInterval = new int[]{2, 10};
        System.out.println(Arrays.deepToString(insert(intervals, newInterval)));
    }
}
